use std::collections::{BinaryHeap, HashMap, HashSet};
use std::cmp::Ordering;
use crate::museum_system::{Museum, EdgeWeight};

/// A*算法节点
#[derive(Debug, Clone)]
struct AStarNode {
    id: String,
    g_cost: f64,  // 从起点到当前节点的实际成本
    h_cost: f64,  // 从当前节点到终点的预估成本
    f_cost: f64,  // 总预估成本 f(n) = g(n) + h(n)
    parent: Option<String>,
}

impl AStarNode {
    fn new(id: String, g_cost: f64, h_cost: f64, parent: Option<String>) -> Self {
        let f_cost = g_cost + h_cost;
        AStarNode {
            id,
            g_cost,
            h_cost,
            f_cost,
            parent,
        }
    }
}

impl PartialEq for AStarNode {
    fn eq(&self, other: &Self) -> bool {
        self.f_cost == other.f_cost
    }
}

impl Eq for AStarNode {}

impl PartialOrd for AStarNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        // 注意：BinaryHeap是最大堆，所以我们需要反转比较
        other.f_cost.partial_cmp(&self.f_cost)
    }
}

impl Ord for AStarNode {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap_or(Ordering::Equal)
    }
}

/// 路径规划器
pub struct PathPlanner {
    eta: f64, // 启发式函数中的权重参数
}

impl PathPlanner {
    pub fn new() -> Self {
        PathPlanner {
            eta: 0.7, // η = 0.7，空间距离权重70%，主题相似度权重30%
        }
    }

    /// 使用A*算法寻找最优路径
    /// 方法1: 子图局部A*优化
    pub fn find_path(
        &self,
        start_id: &str,
        goal_id: &str,
        museums: &HashMap<String, Museum>,
        edge_weights: &HashMap<String, EdgeWeight>,
    ) -> Option<Vec<String>> {
        println!("使用A*算法寻找从 {} 到 {} 的最优路径", start_id, goal_id);
        
        if !museums.contains_key(start_id) || !museums.contains_key(goal_id) {
            println!("起点或终点不存在");
            return None;
        }

        let mut open_set = BinaryHeap::new();
        let mut closed_set = HashSet::new();
        let mut came_from = HashMap::new();
        let mut g_scores = HashMap::new();
        let mut f_scores = HashMap::new();

        // 初始化起点
        let start_h = self.heuristic_function(start_id, goal_id, museums);
        let start_node = AStarNode::new(start_id.to_string(), 0.0, start_h, None);
        open_set.push(start_node);
        g_scores.insert(start_id.to_string(), 0.0);
        f_scores.insert(start_id.to_string(), start_h);

        while let Some(current_node) = open_set.pop() {
            let current_id = &current_node.id;
            
            // 检查是否到达目标
            if current_id == goal_id {
                println!("找到目标，重构路径");
                return Some(self.reconstruct_path(&came_from, current_id));
            }

            closed_set.insert(current_id.clone());

            // 检查动态惩罚项（方法3）
            if self.should_skip_node(current_id, museums) {
                println!("跳过节点 {} (人流量过高)", current_id);
                continue;
            }

            // 探索邻居节点
            for neighbor_id in self.get_neighbors(current_id, edge_weights) {
                if closed_set.contains(&neighbor_id) {
                    continue;
                }

                // 计算从起点经过当前节点到邻居的成本
                let tentative_g_score = g_scores[current_id] + 
                    self.get_edge_weight(current_id, &neighbor_id, edge_weights);

                if !g_scores.contains_key(&neighbor_id) || 
                   tentative_g_score < g_scores[&neighbor_id] {
                    
                    // 更新路径信息
                    came_from.insert(neighbor_id.clone(), current_id.clone());
                    g_scores.insert(neighbor_id.clone(), tentative_g_score);
                    
                    // 计算启发式函数值（方法2）
                    let h_score = self.heuristic_function(&neighbor_id, goal_id, museums);
                    let f_score = tentative_g_score + h_score;
                    f_scores.insert(neighbor_id.clone(), f_score);

                    // 添加到开放集
                    let neighbor_node = AStarNode::new(
                        neighbor_id.clone(),
                        tentative_g_score,
                        h_score,
                        Some(current_id.clone()),
                    );
                    open_set.push(neighbor_node);
                }
            }
        }

        println!("未找到路径");
        None
    }

    /// 方法2: 启发式函数 h(n) 的创新
    /// 公式: h(n) = η·D_{n,goal} + (1-η)·(1-sim(T_n, T_goal))
    fn heuristic_function(&self, node_id: &str, goal_id: &str, museums: &HashMap<String, Museum>) -> f64 {
        let node_museum = &museums[node_id];
        let goal_museum = &museums[goal_id];

        // 计算物理距离 D_{n,goal}
        let distance = self.calculate_distance(node_museum.position, goal_museum.position);
        
        // 计算主题相似度 sim(T_n, T_goal)
        let theme_similarity = self.calculate_theme_similarity(&node_museum.themes, &goal_museum.themes);
        
        // 计算启发式函数值
        let spatial_component = self.eta * distance;
        let theme_component = (1.0 - self.eta) * (1.0 - theme_similarity);
        let heuristic = spatial_component + theme_component;
        
        println!("节点 {} 启发式值: {:.4} (距离: {:.4}, 主题差异: {:.4})", 
            node_id, heuristic, spatial_component, theme_component);
        
        heuristic
    }

    /// 方法3: 动态惩罚项 c(n)
    /// 公式: c(n) = +∞ if 排队人数 ≥ 15, 0 otherwise
    fn should_skip_node(&self, node_id: &str, museums: &HashMap<String, Museum>) -> bool {
        if let Some(museum) = museums.get(node_id) {
            museum.crowd_level >= 15
        } else {
            false
        }
    }

    /// 获取邻居节点
    fn get_neighbors(&self, node_id: &str, edge_weights: &HashMap<String, EdgeWeight>) -> Vec<String> {
        let mut neighbors = Vec::new();
        
        for edge_key in edge_weights.keys() {
            if edge_key.starts_with(&format!("{}->", node_id)) {
                let to_id = edge_key.split("->").nth(1).unwrap();
                neighbors.push(to_id.to_string());
            } else if edge_key.ends_with(&format!("->{}", node_id)) {
                let from_id = edge_key.split("->").next().unwrap();
                neighbors.push(from_id.to_string());
            }
        }
        
        neighbors
    }

    /// 获取边权值
    fn get_edge_weight(&self, from_id: &str, to_id: &str, edge_weights: &HashMap<String, EdgeWeight>) -> f64 {
        let forward_key = format!("{}->{}", from_id, to_id);
        let backward_key = format!("{}->{}", to_id, from_id);
        
        if let Some(edge) = edge_weights.get(&forward_key) {
            edge.updated_weight
        } else if let Some(edge) = edge_weights.get(&backward_key) {
            edge.updated_weight
        } else {
            f64::INFINITY // 如果没有连接，返回无穷大
        }
    }

    /// 重构路径
    fn reconstruct_path(&self, came_from: &HashMap<String, String>, current_id: &str) -> Vec<String> {
        let mut path = vec![current_id.to_string()];
        let mut current = current_id;
        
        while let Some(parent) = came_from.get(current) {
            path.push(parent.clone());
            current = parent;
        }
        
        path.reverse();
        path
    }

    /// 计算欧几里得距离
    fn calculate_distance(&self, pos1: (i32, i32), pos2: (i32, i32)) -> f64 {
        let dx = (pos1.0 - pos2.0) as f64;
        let dy = (pos1.1 - pos2.1) as f64;
        (dx * dx + dy * dy).sqrt()
    }

    /// 计算主题相似度
    fn calculate_theme_similarity(&self, themes1: &[f64], themes2: &[f64]) -> f64 {
        let min_len = themes1.len().min(themes2.len());
        let mut dot_product = 0.0;
        let mut norm1 = 0.0;
        let mut norm2 = 0.0;
        
        for i in 0..min_len {
            dot_product += themes1[i] * themes2[i];
            norm1 += themes1[i] * themes1[i];
            norm2 += themes2[i] * themes2[i];
        }
        
        if norm1 == 0.0 || norm2 == 0.0 {
            return 0.0;
        }
        
        dot_product / (norm1.sqrt() * norm2.sqrt())
    }

    /// 方法4: 跨子图路径合并
    /// 公式: E'_{uv} = E_{uv} · (h(u)/h(v))
    pub fn adjust_boundary_weights(
        &self,
        edge_weights: &mut HashMap<String, EdgeWeight>,
        museums: &HashMap<String, Museum>,
        goal_id: &str,
    ) {
        println!("调整分片边界节点权重");
        
        for edge in edge_weights.values_mut() {
            let h_u = self.heuristic_function(&edge.from, goal_id, museums);
            let h_v = self.heuristic_function(&edge.to, goal_id, museums);
            
            if h_v > 0.0 {
                let weight_adjustment = h_u / h_v;
                edge.updated_weight = edge.weight * weight_adjustment;
                
                println!("边界权重调整 {}->{}: {:.4} -> {:.4} (调整因子: {:.4})", 
                    edge.from, edge.to, edge.weight, edge.updated_weight, weight_adjustment);
            }
        }
    }
} 